package sun.scheduler.util.graph.algorithm.maxflow;

import java.util.ConcurrentModificationException;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import sun.scheduler.util.graph.*;

/**
 * A Residual graph of specified {@link Graph}. With capacities as {@link Edge}
 * values. This implementation only allows edges of the original graph tho
 * connect either Nodes (i, j) or (j, i) but not both at the same time.
 *
 * @author mfj
 */
public final class ResidualGraph extends Graph<Label, ResidualEdgeData>
{

    /**
     * Precission used to compare values.
     */
    public final static double DEFAULT_PRECISION = 1e-5;
    /**
     * Used precission used to compare {@code double} values.
     */
    public final double precision;
    private Graph graph;

    /**
     * Instantiates a new residual graph from a node with flow values. If the
     * graph contains cyclic edges, i.e. edges (i,j) and (j,i) an
     * Illegalargument exception is thrown. The default precision is used for {@code double}
     * value comparison.
     *
     * @param graph the graph that defines the residual capacities
     * @throws IllegalArgumentException if graph contains anticyclic edges
     */
    public ResidualGraph(Graph graph)
    {
        this(graph, DEFAULT_PRECISION);
    }

    /**
     * Instantiates a new residual graph from a node with flow values. If the
     * graph contains cyclic edges, i.e. edges (i,j) and (j,i) an
     * Illegalargument exception is thrown.
     *
     * @param graph the graph that defines the residual capacities
     * @param precision the precision for {@code double} value comparison
     * @throws IllegalArgumentException if graph contains cyclic edges
     */
    public ResidualGraph(Graph graph, double precision)
    {
        super(graph.getNumOfNodes());
        this.graph = graph;
        this.precision = precision;

        for (int i = 0, n = graph.getNumOfNodes(); i < n; i++)
            super.addNode(new Label(precision));
    }

    /**
     * Gets the original graph of this residual graph.
     *
     * @return
     */
    public Graph getGraph()
    {
        return graph;
    }

    /**
     * Adds residual {@link Edge}'s to this {@link ResidualGraph} which computes
     * the residual capacities from the edge which holds some {@link EdgeFlow}
     * data.
     *
     * The {@link EdgeFlow} data gets updatet if duch an edge already exists.
     *
     * @param edge the edge of the underlying graph.
     * @return the forwardEdge edge corresponding to edge
     */
    public Edge<Label, ResidualEdgeData> addEdge(Edge edge, EdgeFlow eData)
    {
        int startId = edge.getStart().id();
        int endId = edge.getEnd().id();

        ResidualEdgeData forward = new ResidualEdgeData(true, eData);
        ResidualEdgeData backward = new ResidualEdgeData(false, eData);

        Edge<Label, ResidualEdgeData> oldEdge = getEdge(startId, endId);
        if (oldEdge != null)
        {
            Edge<Label, ResidualEdgeData> oldOtherEdge = oldEdge.getData().other;
            oldEdge.setData(forward);
            oldOtherEdge.setData(backward);
            return oldEdge;
        }

        Edge<Label, ResidualEdgeData> forwardEdge = super.addEdge(startId, endId, forward);
        Edge<Label, ResidualEdgeData> backwardEdge = super.addEdge(endId, startId, backward);
        forward.other = backwardEdge;
        backward.other = forwardEdge;

        return forwardEdge;
    }

    @Override
    public Edge<Label, ResidualEdgeData> removeEdge(int startId, int endId)
    {
        Edge<Label, ResidualEdgeData> removedEdge = super.removeEdge(startId, endId);
        if (removedEdge != null)
            super.removeEdge(removedEdge.getData().other);
        return removedEdge;
    }

    @Override
    public Edge<Label, ResidualEdgeData> removeEdge(Edge<Label, ResidualEdgeData> edge)
    {
        Edge<Label, ResidualEdgeData> removedEdge = super.removeEdge(edge);
        if (removedEdge != null)
            super.removeEdge(removedEdge.getData().other);
        return removedEdge;
    }

    /**
     * {@inheritDoc} Note that the returned {@link Iterator} is a
     * {@link ResidualBFSIterator} that only consideres edges with nonzero
     * residual capacity.
     */
    @Override
    public BFSIterator<Label, ResidualEdgeData> getBFSIterator()
    {
        return new ResidualBFSIterator(this, precision);
    }

    /**
     * {@inheritDoc} Note that the returned {@link Iterator} is a
     * {@link ConditionedBFSIterator} that only consideres edges with nonzero
     * residual capacity.
     */
    @Override
    public BFSIterator<Label, ResidualEdgeData> getBFSIterator(int id)
    {
        return new ResidualBFSIterator(getNode(id), precision);
    }

    /**
     * {@inheritDoc} Note that the returned {@link Iterator} is a
     * {@link ResidualBFSIterator} that only consideres edges with nonzero
     * residual capacity.
     */
    @Override
    public BFSIterator<Label, ResidualEdgeData> getBFSIterator(Node<Label, ResidualEdgeData> node)
    {
        return new ResidualBFSIterator(node, precision);
    }

    /**
     * Tries to augment a path connecting two nodes with the minimal residual
     * capacity of all edges contained in the path and returns a {@code boolean}
     * value that indicates wheter an augmentable path existed or not.
     *
     * We can run the EdmontKarp Maxflow algorithm by {@code int start = 0, int end = n;
     * while(augmentPath(start,end));}
     *
     * @param startId the id of the start node
     * @param endId the id of the end node.
     * @return {@code true} if a s-t-path was augmentes, {@code false}
     * otherwise.
     */
    public boolean augmentPath(int startId, int endId)
    {
        // get a new iterator that only considers edges with res capacity of zero 
        ResidualBFSIterator iter = new ResidualBFSIterator(getNode(startId), precision);
        Node<Label, ResidualEdgeData> end = getNode(endId);
        while (iter.hasNext())
        {
            Node<Label, ResidualEdgeData> next = iter.next();
            // next is reachable -> augmentable path is found
            if (next != end)
                continue;
            
            double minValue = Double.MAX_VALUE;

            // backtrace path via getPredessesor() and remember min value
            LinkedList<Edge<Label, ResidualEdgeData>> path = new LinkedList<Edge<Label, ResidualEdgeData>>();
            Node<Label, ResidualEdgeData> edgeStart, edgeEnd = next;
            while ((edgeStart = iter.getPredessesor(edgeEnd)) != null)
            {
                Edge<Label, ResidualEdgeData> edge = super.getEdge(edgeStart.id(), edgeEnd.id());

                if (edge.getData().getResidualCapacity() < minValue)
                    minValue = edge.getData().getResidualCapacity();

                path.add(edge);
                edgeEnd = edgeStart;
            }

            // augment all edges with the min value
            for (Edge<Label, ResidualEdgeData> e : path)
                e.getData().augment(minValue);

            return true;

        }

        return false;
    }

}
